//
// Description: 494. 目标和
// Created by Loading on 2022/4/10.
//

#include <bits/stdc++.h>

using namespace std;

/* 动态规划 */
int findTargetSumWays_DP(vector<int> &nums, int target) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    int diff = sum - target;
    // diff的值为两倍的加负号的值，若其为负数或奇数，则不可能组成target
    if (diff < 0 || diff % 2) {
        return 0;
    }
    // 添加负号的元素总和
    int neg = diff / 2;
    /* 0-1背包 */
    // dp[i]表示组成和为 i 的方案数，返回能够组成 neg 的方案数即可
    vector<int> dp(neg + 1);
    dp[0] = 1;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = neg; j >= nums[i]; --j) {
            dp[j] += dp[j - nums[i]];
        }
    }

    return dp[neg];
}

/* 回溯，超时，原因未知 */
int findTargetSumWays(vector<int> &nums, int target) {
    int n = nums.size();
    int res = 0;
    function<void(int, int)> backtrack = [&](int index, int sum) {
        if (index == n) {
            if (sum == target) {
                ++res;
            }
        } else {
            backtrack(index + 1, sum + nums[index]);
            backtrack(index + 1, sum - nums[index]);
        }
    };

    backtrack(0, 0);
    return res;
}

int main() {
    vector<int> nums{28, 29, 35, 48, 9, 9, 3, 22, 43, 0, 33, 3, 3, 11, 44, 39, 35, 0, 25, 8};
    int target = 25;
    auto res = findTargetSumWays(nums, target);
    cout << res << endl;
    res = findTargetSumWays_DP(nums, target);
    cout << res << endl;

    return 0;
}